package algorithms.paixu;

/**
 * @功能
 * @创建时间 2020/12/13
 * 归并算法，将一个数组分成2的倍数方个，将多数组按大小排序成一个数组
 */
public class Merge {
    public static  boolean less(Comparable v,Comparable w){
        return v.compareTo(w)<0;
    }
    public static void exch(Comparable[] a,int i,int j){
        Comparable t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
    private static void show(Comparable[] a){
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }
    public static boolean isSorted(Comparable[] a){
        for (int i = 0; i < a.length; i++) {
            if(less(a[i],a[i-1]))
                return false;

        }
        return true;
    }
    private static Comparable[] aux;

    public static void sort (Comparable[] a){
        aux = new Comparable[a.length];
        sort(a,0,a.length-1);
    }
    public static void sort (Comparable[] a,int lo, int hi){
        if(hi <= lo) return;
        int mid = lo +(hi - lo)/2;
        sort(a,lo,mid);
        sort(a,mid+1,hi);
        merge(a,lo,mid,hi);
    }
    public static void merge(Comparable[] a,int lo,int mid,int hi){
        int i = lo,j = mid + 1;
        for(int k = lo;k <= hi; k++)
            aux[k] = a[k];
        for(int k = lo;k <=hi; k++)
            //判断是否越界
            if (i>mid)                       a[k] = aux[j++];
            else if (j > hi)                 a[k] = aux[i++];
            //首字段比较
            else if (less(aux[j] , aux[i]))  a[k] = aux[j++];
            else                             a[k] = aux[i++];

    }


}
